import java.util.concurrent.Phaser;

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode a1 = null;
        ListNode a2 = null;
        ListNode b1 = null;
        ListNode b2 = null;
        while(pHead != null) {
            if(pHead.val < x) {
                if(a1 == null) {
                    a1 = pHead;
                    a2 = a1;
                } else {
                    a2.next = pHead;
                    a2 = a2.next;
                }
            }
            if(b1 == null) {
                b1 = pHead;
                b2 = b1;
            } else {
                b2.next = pHead;
                b2 = b2.next;
            }
            pHead = pHead.next;
        }
        if(a1 == null) {
            return b1;
        }
        a2.next = b1;
        if(b1 != null)
        {
            b2.next = null;
        }
        return a1;
    }
}
